﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace OneSchema
{
    public class Relation
    {
        // Private members
        private AttributeSet m_attributes;
        private FDSet m_FDs;
        private AttributeSet m_usedAttr, m_unusedAttr;

        private List<AttributeSet> m_keys;          /* cache the keys computed */
        private FDSet m_violatedFDs;                /* cache the FDs that violate either BCNF or 3NF */
        
        /// <summary>
        /// Creates a new relation with specified attributes and fds.
        /// If there are no fds, pass in empty FDSet or null.
        /// </summary>
        public Relation(AttributeSet attributes, FDSet fds)
        {
            m_attributes = attributes;
            m_FDs = ProjectFDs(fds);

            ComputeUsedAndUnusedAttr();
        }

        private void ComputeUsedAndUnusedAttr()
        {
            // Determine used and unused attributes
            m_usedAttr = new AttributeSet();
            m_unusedAttr = new AttributeSet(m_attributes);

            foreach (FD fd in m_FDs)
                m_usedAttr.UnionWith(fd.RHS);

            m_unusedAttr.Minus(m_usedAttr);
        }

        public Relation(AttributeSet attributes)
            : this(attributes, null)
        { }

        public List<AttributeSet> ComputeKeys()
        {
            // Step 1: Trivial FDs
            // Step 2: Unused attr already determined
            // Step 3:
            IEnumerable<AttributeSet> subsets = GenerateFDSubset(m_FDs);

            // Step 4
            List<FD> fdClosures = new List<FD>();
            foreach (AttributeSet attr in subsets)
                fdClosures.Add(new FD(attr, m_FDs.FindAttributeClosure(attr)));

            // Step 5
            var superkeys = (from fd in fdClosures
                            where m_usedAttr.IsSubsetOf(fd.RHS)
                            select fd.LHS).ToList<AttributeSet>();

            // Step 6
            RemoveRedundantKeys(superkeys);

            // Step 7 (Add back unused attr)
            if (superkeys.Count == 0)
                superkeys.Add(new AttributeSet());

            foreach (AttributeSet attr in superkeys)
                attr.UnionWith(m_unusedAttr);

            m_keys = superkeys;

            return superkeys;
        }

        public AttributeSet GetNonPrimeAttributes()
        {
            //throw new NotImplementedException();

            AttributeSet keyUnionSet = new AttributeSet();

            foreach (AttributeSet a in m_keys)
            {
                keyUnionSet.UnionWith(a);
            }

            AttributeSet nonPrimeAttributesSet = new AttributeSet();
            nonPrimeAttributesSet.UnionWith(m_attributes);
            nonPrimeAttributesSet.Minus(keyUnionSet);

            return nonPrimeAttributesSet;
        }

        public void FindViolations(bool BCNF)
        {
            FDSet violatedFDSet = new FDSet();

            foreach(FD fd in m_FDs)
            {
                bool threeNF = (BCNF ? true : !IsConditionThreeSatisfied(fd));
                if (!IsConditionOneSatisfied(fd) && !IsConditionTwoSatisfied(fd) && threeNF)
                {
                    violatedFDSet.Add(fd);
                }
            }

            m_violatedFDs = violatedFDSet;
        }

        public bool Find2NFViolations()
        {
            foreach (FD fd in m_FDs)
            {
                if (!IsConditionOneSatisfied(fd) && !Is2NFConditionSatisfied(fd) && !IsConditionThreeSatisfied(fd))
                {
                    return true;
                }
            }

            return false;
        }

        public Relation Project(AttributeSet attr)
        {
            return new Relation(attr, m_FDs);
        }

        public void Decompose(FD fd, out Relation r1, out Relation r2)
        {
            AttributeSet fdClosure = m_FDs.FindAttributeClosure(fd.RHS);

            r1 = Project(fdClosure);

            AttributeSet tmp = new AttributeSet();
            tmp.UnionWith(m_attributes);
            tmp.Minus(fdClosure);
            tmp.UnionWith(fd.LHS);
            r2 = Project(tmp);

            r1.ComputeKeys();
            r2.ComputeKeys();
        }

        #region Public Properties
        
        public AttributeSet Attributes 
        { 
            get { return m_attributes; }
        }

        public string Name { get; set; }

        public FDSet FunctionalDependencies 
        {
            get { return m_FDs; }
            set
            { 
                m_FDs = ProjectFDs(value);
                ComputeUsedAndUnusedAttr();
            }
        }

        public List<AttributeSet> Keys
        {
            get { return m_keys; }
        }

        public FDSet ViolatedFDs
        {
            get { return m_violatedFDs; } 
        }

        #endregion

        public override string ToString()
        {
            string attr = Attributes.ToString();
            attr = attr.Substring(1, attr.Length - 2);
            return string.Format("{0}({1})", Name, attr);
        }

        #region Private Methods

        /// <summary>
        /// Project FDs relevant to this relation and remove trivial FDs.
        /// </summary>
        private FDSet ProjectFDs(FDSet fdSet)
        {
            FDSet projectedFDs = new FDSet();
            if (fdSet != null)
            {
                foreach (FD fd in fdSet)
                {
                    if (!fd.LHS.IsSubsetOf(m_attributes))
                        continue;

                    // LHS subset of Attr, RHS superset of Attr
                    AttributeSet projectedRHS = new AttributeSet(fd.RHS);
                    projectedRHS.IntersectWith(m_attributes);
                    
                    if (!projectedRHS.isEmpty())
                        projectedFDs.Add(new FD(fd.LHS, projectedRHS));
                }
            }
            projectedFDs.RemoveTrivialFDs();

            return projectedFDs;
        }

        /// <summary>
        /// Step 3....
        /// </summary>
        private IEnumerable<AttributeSet> GenerateFDSubset(FDSet fdSet)
        {
            UniversalBitSet<string> u = new UniversalBitSet<string>();

            AttributeSet unionLHS = new AttributeSet();
            foreach (FD f in fdSet)
                unionLHS.UnionWith(f.LHS);

            foreach (string attr in unionLHS)
                u.Add(attr);

            // Generate subsets of sets
            IEnumerable<BitSet<string>> subsetList = u.GenerateSubsetList();

            List<AttributeSet> retList = new List<AttributeSet>();
            //Parallel.ForEach<BitSet<string>>(subsetList, a =>
            //    {
            //        AttributeSet attr = new AttributeSet();
            //        foreach (string s in a)
            //            attr.Add(s);
            //        retList.Add(attr);
            //    });
            foreach (BitSet<string> a in subsetList)
            {
                AttributeSet attr = new AttributeSet();
                foreach (string s in a)
                    attr.Add(s);
                retList.Add(attr);
            }

            return retList;
        }

        /// <summary>
        /// Step 6....
        /// </summary>
        /// <param name="superkeys"></param>
        private void RemoveRedundantKeys(List<AttributeSet> superkeys)
        {
            List<AttributeSet> redundantKeys = new List<AttributeSet>();
            for (int i = 0; i < superkeys.Count; i++)
            {
                AttributeSet keyToTest = superkeys[i];

                redundantKeys.Clear();
                for (int j = 0; j < superkeys.Count; j++)
                {
                    if (i == j) continue;
                    if (superkeys[j].IsSupersetOf(keyToTest))
                        redundantKeys.Add(superkeys[j]);
                }

                foreach (AttributeSet rkey in redundantKeys)
                    superkeys.Remove(rkey);

                // Update index after removal
                i = superkeys.IndexOf(keyToTest);
            }
        }

        /// <summary>
        /// 3NF and BCNF condition 1 check
        /// </summary>
        /// <param name="fd"></param>
        /// <returns></returns>
        private bool IsConditionOneSatisfied(FD fd)
        {
            return fd.RHS.IsSubsetOf(fd.LHS);
        }

        /// <summary>
        /// 3NF and BCNF condition 2 check
        /// </summary>
        /// <param name="fd"></param>
        /// <returns></returns>
        private bool IsConditionTwoSatisfied(FD fd)
        {
            bool satisfied = false;

            foreach (AttributeSet key in m_keys)
            {
                if (key.IsSubsetOf(fd.LHS)) { satisfied = true; break; }
            }

            return satisfied;
        }

        /// <summary>
        /// 3NF condition 3 check  
        /// </summary>
        /// <param name="fd"></param>
        /// <returns></returns>
        private bool IsConditionThreeSatisfied(FD fd)
        {
            bool satisfied = false;

            AttributeSet a = new AttributeSet();
            a.UnionWith(fd.RHS);
            a.Minus(fd.LHS);

            foreach (AttributeSet key in m_keys)
            {
                if (a.IsSubsetOf(key)) { satisfied = true; break; }
            }

            return satisfied;
        }

        /// <summary>
        /// Check the condition:
        /// LHS of FD is not a proper subset of candidate key for R
        /// To be used in combination with conditions 1 and 3
        /// of 3NF checking
        /// </summary>
        /// <param name="fd"></param>
        /// <returns></returns>
        private bool Is2NFConditionSatisfied(FD fd)
        {
            bool satisfied = false;

            foreach (AttributeSet key in m_keys)
            {
                if (!(fd.LHS.IsSubsetOf(key) && !fd.LHS.SetEquals(key))) { satisfied = true; break; }
            }

            return satisfied;
        }
        #endregion
    }
}
